package solution1.demo.demo1;


import java.util.*;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
public class Solution {

    //1.将有序数组转换为二叉搜索树
    private TreeNode createTree(int[] nums, int left, int right) {
        if(left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        //创建根节点
        TreeNode root = new TreeNode(nums[mid]);
        //递归创建左子树
        root.left = createTree(nums, left, mid - 1);
        root.right = createTree(nums, mid + 1, right);
        return root;
    }

    //2.把二叉搜索树转换为累加树(反中序)
    private int prev;
    public TreeNode convertBST(TreeNode root) {
        if(root == null) {
            return null;
        }
        convertBST(root.right);
        root.val += prev;
        prev = root.val;
        convertBST(root.left);
        return root;
    }

    //3.二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> list = new ArrayList();
            int size = queue.size();
            while(size > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            res.add(list);
        }
        return res;
    }

    //二叉树的层序遍历 II
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList();
            while(size > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            res.add(list);
        }
        Collections.reverse(res);
        return res;
    }

//    //3.二叉树的右视图(dfs)
//    private void dfs(TreeNode root, int depth) {
//        if(root == null) {
//            return;
//        }
//        if(depth > curDepth) {
//            res.add(root.val);
//            curDepth = depth;
//        }
//        dfs(root.right, depth + 1);
//        dfs(root.left, depth + 1);
//    }
//
//    private int curDepth = -1;
//    private List<Integer> res = new ArrayList();
//    public List<Integer> rightSideView(TreeNode root) {
//        dfs(root, 0);
//        return res;
//    }

    //3.二叉树的右视图(bfs)
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size > 0) {
                TreeNode node = queue.poll();
                if(size == 1) {
                    res.add(node.val);
                }
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
        }
        return res;
    }

    //4.填充每个节点的下一个右侧节点指针(bfs)
    public Node connect(Node root) {
        if(root == null) {
            return root;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            Node prevNode = null;
            while(size > 0) {
                Node curNode = queue.poll();
                if(prevNode != null) {
                    prevNode.next = curNode;
                }
                prevNode = curNode;
                if(curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if(curNode.right != null) {
                    queue.offer(curNode.right);
                }
                size--;
            }
        }
        return root;
    }

    //5.翻转二叉树(dfs)
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return root;
        }
        if(root.left != null || root.right != null) {
            //只要有一个不为 null 就交换
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;
        }
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //6.对称二叉树(dfs)
    private boolean isSymmetricChild(TreeNode leftRoot, TreeNode rightRoot) {
        if(leftRoot == null && rightRoot == null) {
            return true;
        }
        if(leftRoot == null && rightRoot != null) {
            return false;
        }
        if(leftRoot != null && rightRoot == null) {
            return false;
        }
        if(leftRoot != null && rightRoot != null) {
            if(leftRoot.val != rightRoot.val) {
                return false;
            }
        }
        return isSymmetricChild(leftRoot.left, rightRoot.right) &&
                isSymmetricChild(leftRoot.right, rightRoot.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }

        return isSymmetricChild(root.left, root.right);
    }

//    //7.二叉树的最大深度(dfs-1)
//    public int maxDepth(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
//    }

    //7.二叉树的最大深度(dfs-2)
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeigh = maxDepth(root.left) + 1;
        int rightHeigh = maxDepth(root.right) + 1;
        return Math.max(leftHeigh, rightHeigh);
    }

    //8.二叉树的最小深度(dfs)
    private void dfs(TreeNode root, int depth) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            //这里才是到达了叶子结点，才开始比较最小值
            if(depth < min) {
                min = depth;
            }
            return;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }

    private int min = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        dfs(root, 1);
        return min;
    }

//    //9.二叉树的最小深度(dfs)
//    public int minDepth(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        if(root.left != null && root.right != null) {
//            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
//        }
//        if(root.left != null) {
//            return minDepth(root.left) + 1;
//        }
//        if(root.right != null) {
//            return minDepth(root.right) + 1;
//        }
//        return 1;
//    }

    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null) {
            return 1;
        }
        int leftCount = countNodes(root.left) + 1;
        int rightCount = countNodes(root.right) + 1;
        return leftCount + rightCount + 1;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return createTree(nums, 0, nums.length - 1);
    }

//    //10.完全二叉树的节点个数(dfs)
//    public int countNodes(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        if(root.left == null) {
//            return 1;
//        }
//        return countNodes(root.left) + countNodes(root.right) + 1;
//    }



}

class Main {
    public static void main(String[] args) {

        Solution solution = new Solution();
    }
}
